package pyip.lib.javalearn.algorithm.sort;


/**
 * 直接插入排序<br>
 * 基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，<br>
 * 现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
 * @author yepeng
 * @date 2015年9月2日
 */
public class InsertSort implements Sort {

    public void sort(int[] arr, boolean asc) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int temp = 0;
        for (int i = 1; i < arr.length; i++) {
            int j = i - 1;
            temp = arr[i];
            for (; j >= 0 && (asc ? temp < arr[j] : temp > arr[j]); j--) {
                arr[j + 1] = arr[j]; // 将大于(asc)/小于(desc)temp的值整体后移一个单位
            }
            arr[j + 1] = temp;
        }
    }

}
